#ifndef GRAPH_H
#define GRAPH_H

#include <QDataStream>
#include <QFile>
#include <QList>
#include "arc.h"
#include "summit.h"

class QDataStream;

template <typename T>
class Graph {
  template <typename Y>
  friend QDataStream& operator<<(QDataStream& out, const Graph<Y>& graph);
  template <typename Y>
  friend QDataStream& operator>>(QDataStream& in, Graph<Y>& graph);

  public:
    // Publics Methods
    Graph() {}
    Graph(int summitsNumber);
    int summitsNumber() const;
    int arcsNumber() const;
    virtual const Summit<T>& getSummit(int summitNumber) const;
    virtual void setSummit(int summitNumber, const Summit<T>& summit);
    virtual const Arc<T>& getArc(int arcNumber) const;
    virtual void setArc(int arcNumber, const Arc<T>& arc);
    virtual int addSummit(const QString& name, const T& info);
    virtual void removeSummit(int number);
    virtual void addArc(int source, int destination, const T& info = 1, const QString& name = "");
    virtual void removeArc(int source, int destination);
    virtual void toFsAps(int*& fs, int*& aps);
    virtual void toAdjacentMatrix(int**& A) const;
    QDataStream& operator<<(QDataStream& out);
    QDataStream& operator>>(QDataStream& out);
    bool open(const QString& filename);
    bool save(const QString& filename) const;

  private:
    // Privates Attributes
    QList<Summit<T> > summitsList;
    QList<Arc<T> > arcsList;
};

// Constructor
template <typename T>
Graph<T>::Graph(int summitsNumber) {
  for(int i = 0; i < summitsNumber; ++i) summitsList.append(Summit<int>());
}

// Return summits number
template <typename T>
int Graph<T>::summitsNumber() const {    void addArc(const Arc<T>& arc);
  return summitsList.count();
}

// Return arcs number
template <typename T>
int Graph<T>::arcsNumber() const {
  return arcsList.count();
}

// Return summit by number
template <typename T>
const Summit<T>& Graph<T>::getSummit(int summitNumber) const {
  return summitsList[summitNumber];
}

// Set summit by number
template <typename T>
void Graph<T>::setSummit(int summitNumber, const Summit<T>& summit) {
  summitsList[summitNumber] = summit;
}

// Return arc by number
template <typename T>
const Arc<T>& Graph<T>::getArc(int arcNumber) const {
  return arcsList[arcNumber];
}

// Set arc by number
template <typename T>
void Graph<T>::setArc(int arcNumber, const Arc<T>& arc) {
  arcsList[arcNumber] = arc;
}

// Add a summit to the graph
template <typename T>
int Graph<T>::addSummit(const QString& name, const T& info) {
  summitsList.append(Summit<T>(name, info));
  return summitsNumber() + 1;
}

// Remove a summit to the graph
template <typename T>
void Graph<T>::removeSummit(int number) {
  for(int i = 0; i < summitsNumber(); ++i)
      for(int j = 0; j < arcsNumber(); ++j)
        if(getArc(j).getSource() == number || getArc(j).getDestination() == number) arcsList.removeAt(j);
  summitsList.removeAt(number + 1);
}

// Add an arc to the graph
template <typename T>
void Graph<T>::addArc(int source, int destination, const T& info, const QString& name) {
  for(int i = 0; i < summitsNumber(); ++i)
      for(int j = 0; j < arcsNumber(); ++j)
        if(getArc(j).getSource() == source && getArc(j).getDestination() == destination) return;

  arcsList.append(Arc<T>(source, destination, info, name));
}


// Remove an arc to the graph
template <typename T>
void Graph<T>::removeArc(int source, int destination) {
  for(int i = 0; i < summitsNumber(); ++i)
      for(int j = 0; j < arcsNumber(); ++j)
        if(getArc(j).getSource() == source && getArc(j).getDestination() == destination) arcsList.removeAt(j);

}

// Convert the graph to fs list and aps list
template <typename T>
void Graph<T>::toFsAps(int*& fs, int*& aps) {
  fs = new int[arcsNumber() + summitsNumber() + 1];
  fs[0] = arcsNumber() + summitsNumber();
  aps = new int[summitsNumber() + 1];
  aps[0] = summitsNumber();

  int pos = 1;
  for(int i = 0; i < summitsNumber(); ++i) {
      aps[i + 1] = pos;
      for(int j = 0; j < arcsNumber(); ++j)
        if(getArc(j).getSource() == i + 1) fs[pos++] = getArc(j).getDestination();
      fs[pos++] = 0;
  }
}

// Operator << for serialization (writing)
template <typename T>
QDataStream& operator<<(QDataStream& out, const Graph<T>& graph) {
  return out << graph.summitsList << graph.arcsList;
}

// Operator >> for serialization (reading)
template <typename T>
QDataStream& operator>>(QDataStream& in, Graph<T>& graph) {
  return in >> graph.summitsList >> graph.arcsList;
}


template <typename T>
bool Graph<T>::open(const QString& filename) {
  QFile file(filename);
  if(!file.open(QIODevice::ReadOnly)) return false;

  QDataStream out(&file);
  out >> (Graph<T>&)*this;

  file.close();

  return true;
}

template <typename T>
bool Graph<T>::save(const QString& filename) const {
  QFile file(filename);
  if(!file.open(QIODevice::WriteOnly)) return false;

  QDataStream out(&file);
  out << (Graph<T>&)*this;

  if(!file.flush()) return false;
  file.close();

  return true;
}

template <typename T>
void Graph<T>::toAdjacentMatrix(int**& A) const {

  A = new int*[summitsNumber() + 1];
  A[0] = new int[summitsNumber()];
  for(int i = 0; i <= summitsNumber(); ++i) A[0][i] = 0;

  A[0][0] = summitsNumber();
  A[0][1] = arcsNumber();

  for(int i = 1; i <= summitsNumber(); ++i) {
    A[i] = new int[summitsNumber() + 1];
    A[i][0] = 0;

    for(int j = 1; j <= summitsNumber(); ++j) {
      A[i][j] = 0;
      for(int k = 0; k < arcsNumber(); ++k)
        if(getArc(k).getSource() == i && getArc(k).getDestination() == j) A[i][j] = 1;
    }
  }
}

#endif
